from typing import List


class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        size = len(nums)

        suffix = list(nums)
        for i in range(size - 2, -1, -1):
            suffix[i] = max(nums[i], suffix[i + 1])

        ans = 0

        for i1 in range(size - 3):
            for i2 in range(i1 + 1, size - 2):
                if nums[i1] + nums[i2] >= suffix[i2 + 1]:
                    continue
                for i3 in range(i2 + 1, size - 1):
                    if nums[i1] + nums[i2] + nums[i3] > suffix[i3 + 1]:
                        continue
                    for i4 in range(i3 + 1, size):
                        if nums[i1] + nums[i2] + nums[i3] == nums[i4]:
                            ans += 1

        return ans


if __name__ == "__main__":
    print(Solution().countQuadruplets(nums=[1, 2, 3, 6]))  # 1
    print(Solution().countQuadruplets(nums=[3, 3, 6, 4, 5]))  # 0
    print(Solution().countQuadruplets(nums=[1, 1, 1, 3, 5]))  # 4
